package 我的Java学习_算法基础.day_08;

import java.util.Scanner;

/**
 * @author 挚爱之夕
 * @date 2021/8/23 - 08 - 23 - 13:31
 * @Description: 我的Java学习.day_08
 * @Version: 1.0
 */
public class _122_硬币支付 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 0; i < 6; i++) {
            counts[i] = sc.nextInt();
        }
        int n = sc.nextInt();
        int t = solve(n,5);
        System.out.println(t);
    }

    /**
     * coins 面值
     * counts 各面值对应拥有的数量
     * count 最少支付硬币数
     */
    static int[] coins = {1,5,10,50,100,500};
    static int[] counts=new int[6];
    static int count = 0;


    /**
     *
     * @param n 应支付钱数
     * @param index coins.length-1 即从最大面值开始取
     * @return 支付最少硬币数
     */
    private static int solve(int n,int index){
        if(n<0||index<0) return -1;
        if(n==0){
            return count;
        }
        int want = n/coins[index];
        int have = counts[index];
        int put = Math.min(want,have);
        count+=put;
        return solve(n-coins[index]*put,index-1);
    }
}
